As will be appreciated by those skilled in the art, communication networks and their operations can be described according to the Open Systems Interconnection (OSI) model which includes seven layers including an application, presentation, session, transport, network, link, and physical layer. The OSI model was developed by the International Organization for Standardization (ISO) and is described in "The Basics Book of OSI and Network Management" by Motorola Codex from Addison-Wesley Publishing Company, Inc., 1993 (First Printing September 1992).
Each layer of the OSI model performs a specific data communications task, a service to and for the layer that precedes it (e.g., the network layer provides a service for the transport layer). The process can be likened to placing a letter in a series of envelopes before it's sent through the postal system. Each succeeding envelope adds another layer of processing or overhead information necessary to process the transaction. Together, all the envelopes help make sure the letter gets to the right address and that the message received is identical to the message sent. Once the entire package is received at its destination, the envelopes are opened one by one until the letter itself emerges exactly as written.
In a data communication transaction, however, each end user is unaware of the envelopes, which perform their functions transparently. For example, an automatic back teller transaction can be tracked through the multilayer OSI system. One multiple layer system (Open System A) provides an application layer that is an interface to a person attempting a transaction, while the other multiple layer system (Open System B) provides an application layer that interfaces with applications software in a bank's host computer. The corresponding layers in Open Systems A and B are called peer layers and communicate through peer protocols. These peer protocols provide communication support for a user's application, performing transaction related tasks such as debiting an account, dispensing currency, or crediting an account.
Actual data flow between the two open systems (Open System A and Open System B), however, is from top to bottom in one open system (Open System A, the source), across the communications line, and then from bottom to top in the other open system (Open System B, the destination). Each time that user application data passes downward from one layer to the next layer in the same system more processing information is added. When that information is removed and processed by the peer layer in the other system, it causes various tasks (error correction, flow control, etc.) to be performed.
The ISO has specifically defined all seven layers, which are summarized below in the order in which the data actually flows as they leave the source:
Layer 7, the application layer, provides for a user application (such as getting money from an automatic bank teller machine) to interface with the OSI application layer. That OSI application layer has a corresponding peer layer in the other open system, the bank's host computer. PA1 Layer 6, the presentation layer, makes sure the user information (a request for $50 in cash to be debited from your checking account) is in a format (i.e., syntax or sequence of ones and zeros) the destination open system can understand. PA1 Layer 5, the session layer, provides synchronization control of data between the open systems (i.e., makes sure the bit configurations that pass through layer 5 at the source are the same as those that pass through layer 5 at the destination). PA1 Layer 4, the transport layer, ensures that an end-to-end connection has been established between the two open systems and is often reliable (i.e., layer 4 at the destination "confirms the request for a connection," so to speak, that it has received from layer 4 at the source). PA1 Layer 3, the network layer, provides routing and relaying of data through the network (among other things, at layer 3 on the outbound side an "address" gets slapped on the "envelope" which is then read by layer 3 at the destination). PA1 Layer 2, the data link layer, includes flow control of data as messages pass down through this layer in one open system and up through the peer layer in the other open system. PA1 Layer 1, the physical interface layer, includes the ways in which data communications equipment is connected mechanically and electrically, and the means by which the data moves across those physical connections from layer 1 at the source to layer 1 at the destination.
The particular focus of the following discussion is on media access control (MAC) for communication networks which is performed in the OSI network and data link layers. It will be appreciated by those skilled in the art that various applications and components operating in the other OSI layers may be interchangeably used with the particular MAC described below so long as these applications and components adhere to the OSI design structures. For example, many different OSI physical layer components (e.g., a parallel bus, a serial bus, or a time-slotted channel) can be used in conjunction with the same MAC so long as each of the OSI physical layer components passes the particular information required by OSI design parameters to the OSI data link layer.
One particular type of communication network is the ring network. Ring nets use a series of point-to-point cables, either twisted pair or coaxial, connected between consecutive stations. The interfaces (i.e., nodes) connected to the ring nets are active (i.e., not passive like carrier sense networks).
A major issue in the design and analysis of ring nets is the "physical length" of a bit. If the data rate of the ring is R Mega bits per second (Mbps), a bit is emitted every 1/R microseconds (.mu.sec). Bits are transmitted serially, just as with the Ethernet. With a typical signal propagation speed of 200 meters/.mu.sec, each bit occupies 200/R meters on the ring. This means, for example, that a 1 Mbps ring whose circumference is 1000 meters can contain only 5 bits on it at once. The implications of the number of bits on the ring will become clearer later.
In all rings there is a need for the conceptual equivalent of a master clock telling each station to read one input bit and write one output bit. This master clock typically is implemented as clock signal line having encoded 0 bits as a positive pulse followed by a negative pulse, and encoded 1 bits as a negative pulse followed by a positive pulse (or vice versa). This way an idle ring still has a well defined bit pattern on it (all zeros), and timing is provided by the leading edges of the data bits themselves, without the use of a master clock.
The oldest and most popular kind of ring net is a token ring. In this kind of ring a special bit pattern, called the token, circulates around the ring whenever all stations are idle. Typically, the token will be a special 8-bit pattern, for example, 11111111. Bit stuffing is used to prevent this pattern from occurring in the data.
When a station wants to transmit a packet, it is required to seize the token and remove it from the ring before transmitting. To remove the token, the ring interface, which connects the station to the ring, must monitor all bits that pass by. As the last bit of the token passes by, the ring interface inverts it, changing the token (e.g., 11111111) into another bit pattern, known as a connector (e.g., 11111110). Immediately after the token has been so transformed, the station making the transformation is permitted to begin transmitting.
This organization has several important implications for the ring design. To start with, after reading all but the last bit of a (potential) token, the interface must be able to read the last bit and decide whether or not to invert it before forwarding any part of the bit. If the preceding bit pattern is a token, the final bit must be inverted. However, if the final bit shows that the bit pattern is not a token, that is, it is just some data, the final bit must not be inverted. This requirement means that each arriving bit must be stored in its entirety, and then a new bit generated, thereby creating a 1-bit delay in each ring interface. If there are many stations on the ring, the cumulative effect of these 1-bit delays has an important impact on the performance of the ring.
Another implication of the token ring design is that the ring itself must have a sufficient delay to contain a complete token to circulate when all stations are idle. The delay has two components: the 1-bit delay introduced by each station, and the signal propagation delay. In almost all rings, the designers must assume that stations may be powered down at various times, especially at night. If the interfaces are powered from the ring, shutting down the station has no effect on the interface, but if the interfaces are powered externally, they must be designed to connect the input to the output when power goes down, thus removing the 1-bit delay. The point here is that on a short ring an artificial delay may have to be inserted into the ring at night to ensure that a token can be contained on it.
Ring interfaces have two operating modes, listen and transmit. In listen mode, the input bits are simply copied to output, with a delay of one bit time. In transmit mode, which is entered only after the token has been seized, the interface breaks the connection between input and output, entering its own data onto the ring. To be able to switch from listen to transmit mode in 1 bit time, the interface usually needs to buffer one or more packets itself rather than having to fetch them from the station on such short notice.
As bits that have propagated around the ring come back, they are removed from the ring by the sender. The sending station can either save them, to compare with the original data to monitor ring reliability, or discard them. This ring architecture puts no limit on the size of the packets, because the entire packet never appears on the ring at one instant. After a station has finished transmitting the last bit of its packet, it must regenerate the token. When the last bit of the packet has gone around and come back, it must be removed, and the interface must switch back into listen mode immediately, to avoid removing the token or connector that follows.
It is straightforward to handle acknowledgments on a token ring. The packet format need only include a 1-bit field for acknowledgments, initially zero. When the destination station has received a packet, it need only invert the bit. Of course, if the acknowledgment means that the checksum has been verified, the bit must follow the checksum, and the ring interface must be able to verify the checksum as soon as its last bit has arrived. When a packet is broadcast to multiple stations, a more complicated acknowledgment mechanism must be used (if any is used at all).
When traffic is light, the token will spend most of its time idly circulating around the ring. Occasionally a station will convert it to a connector, followed by a packet and then a new token. However, when the traffic is heavy, so that there is a queue at each station, as soon as a station finishes its transmission and regenerates the token, the next station downstream will see and remove the token. In this manner the permission to send rotates smoothly around the ring, in round-robin fashion. Since there is only one token, there is never any contention as in the Ethernet. Higher level protocols decide whether a station must regenerate the token after one packet, or whether it may empty its entire queue first.
Although the token ring and Ethernet differ in many details, they also have many things in common. Since they use similar technologies, they can operate at similar data rates. In both cases stations must first acquire the channel before transmitting, with channel acquisition done by waiting for the token in one case and by contention in the other. Both systems have a channel efficiency determined by this wait time and transmission time. As the data rate is dramatically increased, say by using a fiber-optics medium, both networks' channel efficiency drops toward zero, because the channel-acquisition time in both cases depends on signal propagation speed, and this is not affected by increasing the data rate. Because the propagation time enters into the channel-acquisition time, both networks suffer from increased cable length, Ethernets due to increased contention slot size and token rings due to increased walk time. Under conditions of heavy load the ring operates as a round-robin, as do most of the Ethernet protocols, although the Ethernet protocols must be quite sophisticated to achieve this effect, whereas it happens automatically on the ring.
As long as 100% of the hardware and software functions flawlessly, the token ring works fine. However, if the token is ever accidentally lost, the system is in deep trouble. The traditional approach to solving the missing-token problem is to have each interface start a timer immediately prior to its searching for a token. The timer must be set to the worst case, namely all N=1 other stations have a maximum length packet to transmit. If the timer goes off, the interface knows that there has been a mishap, so it puts a token onto the ring and hopes for the best. Unfortunately, two or more interfaces may put tokens onto the ring at the same time, making the problem even worse.
The regeneration of lost tokens is essentially the same arbitration problem as channel allocation in the Ethernet. Another kind of ring net, called a contention ring, utilizes a contention mechanism, required for token recovery, to eliminate the channel-acquisition delay when the load is light.
Unlike the token ring, which contains a circulating token when there is no traffic, the contention ring contains nothing at all when there is no traffic. In this respect it is like the Ethernet. When a station has a packet to transmit, it checks to see if a bit is currently passing through its interface. If there is not traffic, it just starts transmission. At the end of its packet, it puts a token onto the ring, just as the token ring does. However, unlike the token ring, it also removes the token when the packet comes around again.
Now consider how a station behaves when it notices traffic on the ring at the time it wants to send. It just waits for the token, and as in the token ring, inverts the last bit, thus converting it to a connector. Directly following the connector it begins transmitting its own packet. Since the token is now missing, no other station can seize it, so there is no contention. Once the ring is completely full of bits (e.g., when the load is high), no station will ever transmit unless it has acquired the token. Consequently, under conditions of high load, the contention ring acts just like a token ring.
If exactly one station decides to begin transmitting onto an idle ring, then one station puts data onto the ring and the same station removes it. However, trouble occurs when two stations simultaneously decide to transmit onto an idle ring. In this case, the data that each station absorbs is the data the other station put onto the ring. Depending on the positions of the two stations, the packet may well be removed before it gets to the destination, hardly an acceptable situation. Fortunately each station can recognize that what it is receiving is not what it sent, especially if packets begin with the sender's address. When a station detects that such a collision has occurred, it terminates its transmission but keeps on absorbing data until there is no more. Eventually, the ring becomes quiet again, both stations wait random amounts of time, and the contention begins anew.
In summary, the contention ring has low channel-acquisition delay when it is lightly loaded, and the properties of the token ring when it is heavily loaded, the price paid being the occurrence of contention even when the hardware is functioning properly. Another point is the inability of a station to know whether or not it has acquired the channel until its first few bits have passed all the way around, been absorbed, and analyzed. In contrast, a token ring station knows immediately when it has captured the token, and an Ethernet station knows whether it has been successful within one round-trip propagation time of the Ethernet due to the 1-bit delays in each station, so the contention ring has the longest channel-acquisition time of the three systems. A plus point for the contention ring over the Ethernet is that it uses only digital logic. It detects collisions by looking at bit patterns, not by analyzing analog waveforms as the Ethernet does.
Each of the previous rings normally operates with one packet on the ring. The next two rings normally operate with multiple packets on the ring. The first of these is the slotted ring, so-called because it is slotted into a number of fixed-size packets. Unless the physical distance around the ring is very large or there are many stations, it is unlikely that there will be enough delay to hold several packets, so artificial delays are needed. These can be obtained easily by putting shift registers in the ring interfaces. Instead of the 1-bit delay as in the other ring nets, there are multiple-bit delays.
Each packet slot contains a bit that tells whether the slot is full or empty. When a station wishes to transit, it simply waits for an empty slot to come around, marks it as full, and puts its data in the slot. Of course, packets must be small enough to fit in a packet slot, in contrast to the token and contention rings, both of which support packets of arbitrarily large size.
The last kind of ring, the register insertion ring, is a more sophisticated version of the slotted ring. The interface contains two registers, a shift register and an output buffer. When a station has a packet to transmit, it loads the packet into the output buffer. Packets may be variable length, up to the size of the output buffer.
When the ring is started up, the input pointer points to the rightmost bit position in the shift register, meaning that all the bit slots including and to the left of where it is pointing are empty. When a bit arrives from the ring, it is placed at the position pointed to by the input pointer, and the pointer is moved 1 bit to the left. As soon as the address field of the packet has arrived, the interface can determine whether or not the packet is addressed to it. If so, the rest of the packet is diverted to the station, removing the packet from the ring. The input pointer is then reset to the extreme right.
If, however, the packet is not addressed to the location station, the interface begins forwarding it. As each new bit arrives, it is put in the place pointed to by the input pointer. The entire contents of the shift register is then shifted right one position, pushing the rightmost bit out onto the ring. The input pointer is not advanced. If no new input arrives, for example due to an interpacket gap, the contents of the shift register can be reduced by 1 bit and the input pointer moved right one position.
Whenever the shift register has pushed out the last bit of a packet, it checks to see if (1) there is an output packet waiting, and (2) the number of empty slots in the shift register is at least as large as the output packet. Only if both conditions are met can output proceed, in which case the output switch is flipped and the output buffer is now shifted out of the ring, 1 bit at a time, in synchronization with the input. New input is accumulated in the shift register, which is why there must be enough empty slots there to accommodate all the input while the output buffer is being emptied. Not all the slots may be needed, since an interpacket gap may arrive during output, but the interface must be prepared for the worst case. As soon as the output buffer has been emptied, the switch is flipped again, and the shift register is emptied (if it has anything in it).
An interesting property of this ring architecture is the way it prevents a station from monopolizing the ring. If the ring is idle, the shift register will be empty when an output packet has been finished, so the next output packet can be sent as soon as it can be loaded into the output buffer by the station. In effect, if the ring is idle, any station can have the entire bandwidth it so desires. If the ring is busy, however, after sending a packet the station will not be allowed to send another one because there will usually be insufficient empty slots in the shift register. Only when enough interpacket gaps have been saved up can output occur again. In essence, to send a b-bit packet, the interface must accumulate b bits worth of empty space on the ring in which to insert the packet. The b bits need not be consecutive, however, because the interpacket gaps are accumulated in the left-hand portion of the shift register.
Slotted rings are particularly suitable for high speed local area networks (LANs) and may work in some wide area network (WAN) environments.
One particular slotted ring is an Orwell ring. The Orwell ring has the most efficient access protocol of all the slotted rings due to the destination release of the slots.
The basic access mechanism (AM) (i.e., the basic MAC protocol) of Orwell consists of having a ring partitioned into equal length slots. Slots circulate around the ring and can be empty or full. A full slot is occupied by a mini-packet (i.e., a MAC protocol data unit (PDU)). Stations (nodes) are actively coupled to the ring. They repeat or modify the slots. An empty slot may be filled by a mini-packet, if there is one. A full slot circulating around the ring, reaches the destination station which reads it and passes it on to a higher OSI layer. Each station is capable of using every empty slot that arrives and of reading every slot destined to itself.
There are two classes of basic slotted ring AMs depending on which station empties a full slot; the source station, or the destination station. After emptying the slot there are two possibilities: the slot can be used by the station that empties it, or it must be passed to the next downstream station.
Orwell implements the following basic AM. The destination station releases a slot that was full and the next downstream station may use it. More than one slot at a time can be carrying mini-packets from the same source.
The Orwell MAC protocol recognizes two service classes: class 1 for delay sensitive services, requiring a guaranteed bandwidth, e.g., synchronous traffic, and class 2 for the delay tolerant services, e.g., asynchronous data. Access is organized in intervals. Each station on the ring has a counter indicating the number of packets allowed to be sent during the interval. This way load control is provided.
Another ring network, called a Cambridge ring, maximizes the timing tolerance and minimizes the delay at the source and destination. In the Cambridge ring, the leading bit is always a one and is followed by a one and is followed by a bit to indicate whether the slot is full or empty. A control bit follows that is used by the monitor station (node) to mark as empty packets which are circulating indefinitely due to an error in the full/empty bit. This is followed by 4 eight bit bytes the first two of which are used for destination and source addresses and the last two for data. Finally there are two control bits used for acknowledgment purposes and a parity bit used for ring maintenance.
When a station (node) has a packet ready for transmission in its shift register it waits until the beginning of the next slot. It now reads the full/empty bit and at the same time writes a one at the output. If the full/empty bit was a zero it transmits the packet, if however the full/empty bit was a one the slot is already occupied and the algorithm is repeated for the next packet. This scheme minimizes the delay at each node.
The transmitted packet makes its way to the destination where the control bits are set on the fly to indicate accepted, busy, or rejected. It now returns to the source where the slot is marked empty. If the packet returns with the control bits unchanged it was not recognized by any destination. Each station knows the total number of slots in the ring and can thus clear the full/empty bit immediately.
Thus, on transmission, the packet is delayed until an empty slot is found but then the transmission is rapid. This is in contrast to the register insertion scheme where the delay around the ring can be large but the initial delay before the register is inserted is small. As the destination does not explicitly signal when it is ready to receive the next packet, the ring can easily become clogged with packets returning marked busy when devices with varying speed characteristics are being interconnected. In order to overcome this, the following algorithm is incorporated in the hardware to reduce the number of busies. If a source transmits a packet and it returns marked busy, then it is not allowed to retransmit it until some time later. This additional delay is dependent on ring loading and is approximately the time to acquire the next empty slot. If any further retransmissions are attempted, the extra delay is increased to about 16 times the original delay. Thus, the number of busies is decreased and performance is improved.
Each station possesses a station select register which is initialized by the host. This register can be set to accept or to reject all packets, or to receive from one source only. When combined with a time out mechanism it can be used to allocate resources on the ring.
A need exists for a MAC protocol of a slotted ring that is ideally suited for broadband communication networks. These networks require a high throughput data bus that can handle traffic loads that are both uniformly and geometrically distributed on the network. These broadband networks (e.g., high speed packet switching, real time video compression, real time multimedia coding, and real time security algorithm processing) have transfer rates approaching 1 gigabyte per second and as such require new solutions to remove processing bottlenecks. Since, the processing power of current processors is limited, many of these tasks need to be parallelized to multiple processors. Thus, a better MAC protocol and system for using the protocol are needed which are both efficient and cost-effective and can be used as an interconnection network for high speed multiprocessor applications.
The present invention provides a solution to these and other problems, and offers other advantages over the prior art.